package LiKou;

import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: H_tao_X
 * Date: 2022-12-15
 * Time: 13:17
 */
public class _twoNumI {
    public static void main(String[] args) {

    }


    /**
     * 1. 两数之和 输入数组是 无序数组
     */

    // 1. 循环遍历  -- > 0(n^2)
    public static int[] twoSum(int[] nums,int target) {
        int n = nums.length;
        for(int i = 0;i < n;i++) {
            for (int j = i+1; j < n; j++) {
                if(nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }
        // 不满足返回 int[0]
        return new int[0];
    }



    // 2. 哈希查找 - > 时间复杂度为 0(n)
    public static int[] twoSum1(int[] nums,int target) {
        // 判空
        if(nums == null || nums.length == 0){
            return new int[0];
        }
        // 创建 hashMap 存储 元素，以及对应的下标
        HashMap<Integer,Integer> hashMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i],i); // O(n)
        }

        // 遍历数组
        for (int i = 0; i < nums.length; i++) { // O(n)
            int x = nums[i];
            // 目标值 - x 如果 被 hashMap 包含在内，就返回对应下标
            if(hashMap.containsKey(target - x)) {
                int index = hashMap.get(target - x);
                // 这里 index 和 i 可能是同一个元素，这里需要判断一下
                if(i != index) {
                    return new int[]{i,index};
                }
            }
        }
        return new int[0];
    }


    // 哈希 优化
    public static int[] twoSum2(int[] nums,int target) {
        // 判空
        if(nums == null || nums.length == 0){
            return  new int[0];
        }
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if(hashMap.containsKey(target - x)) {
                int index = hashMap.get(target - x);
                return new int[]{i,index};
            }
            hashMap.put(x,i);
        }
        return new int[0];
    }

    /**
     * 力扣：167
     * 两数之和，输入的数组是 有序 数组
     * 且 下标值 是从 1开始，而不是 0，不可以重复使用相同的元素
     *  输入 ：nums[2,7,11,15] target = 9
     *  输出 ：[1,2]
     *  解释：2 + 7 = 9，因此 index1 = 1，index2 = 2
     */

    // 二分查找 O （log^n）





}
